import { BSTree } from "./00_二叉搜索树BSTree";
import { AVLTreeNode } from "./04_封装AVLTreeNode(左旋转操作)";
class AVLTree<T> extends BSTree<T> {
    //  如何找到不平衡的节点，先不管?

    // 假设已经找到了,那我们如何将这个节点变平衡
    // root 找到的不平衡的节点 根据不平衡的节点LL/RR/LR/RL让子树平衡
    rebalance(root: AVLTreeNode<T>){
        const pivot = root.higherChild;
        const current = pivot?.higherChild;

        let resultNode: AVLTreeNode<T> | null = null;

        if(pivot?.isLeft){ // L left
            if(current?.isLeft){ // LL left left
                root.rightRotation()
            }else{ // LR left right
                pivot.leftRotation()
                // 左旋和右旋都将旋转后的根节点返回出去了，所以这里的resultNode是新的根节点
                resultNode = root.rightRotation()
            }
        }else{// R right
            if(current?.isRight){ //RL right left
                pivot?.rightRotation();
                resultNode = root.leftRotation();
            }else{// RR right right
                root.leftRotation();
            }
        }
        // 判断返回的pivot是否有父节点
        if(!resultNode?.parent){
            this.root = resultNode
        }
    }

}

const avlTree = new AVLTree<number>()

avlTree.insert(10)
avlTree.insert(15)
avlTree.insert(20)
avlTree.insert(5)
avlTree.insert(8)

avlTree.print()